package com.demo.java.OD301_350.OD309;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最佳植树距离、种树(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146104310
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取坑位数量
        int n = scanner.nextInt();

        // 读取所有坑位的位置
        int[] holes = new int[n];
        for (int i = 0; i < n; i++) {
            holes[i] = scanner.nextInt();
        }

        // 读取需要种植的树苗数
        int target = scanner.nextInt();

        // 排序坑位，确保贪心选择时能按顺序遍历
        Arrays.sort(holes);

        // 二分查找范围，最小可能距离为 0，最大可能距离为 (最大坑位 - 最小坑位)
        int left = 0;
        int right = holes[holes.length - 1] - holes[0];
        int answer = -1;

        // 二分查找最大化最小间距
        while (left <= right) {
            int mid = left + (right - left) / 2; // 当前尝试的最小间距
            int count = 1; // 至少种 1 棵树（第一棵）
            int previous = holes[0]; // 记录上一次种植的坑位位置

            // 遍历坑位，尝试种植 target 棵树
            for (int i = 1; i < holes.length; i++) {
                // 如果当前坑位与上一个种植的坑位距离 >= mid，则可以种植
                if (holes[i] - previous >= mid) {
                    count++;
                    previous = holes[i]; // 更新最近种植的树坑位

                    // 如果已经种够 target 棵树
                    if (count >= target) {
                        answer = mid; // 记录当前合法的间距
                        left = mid + 1; // 尝试更大的最小间距
                        break;
                    }
                }
            }

            // 如果最终没种满 target 棵树，则缩小间距
            if (count < target) {
                right = mid - 1;
            }
        }

        // 输出最大化的最小间距
        System.out.println(answer);
    }
}